package com.cty.Stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
*
*将中缀表达式转化为后缀表达式
*
* */
public class conversion {
    public static void main(String [] args) {
        String expression = "5+8*2";
        List<String> list = conversion.toInFixExpression(expression);
        System.out.println(list);
        //创建好的两个栈对象
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        for (String elem : list) {
            if (isOper(elem)) {
                if (elem.equals("(") || s1.isEmpty()) {
                    s1.push(elem);
                } else if (elem.equals(")")) {
                    while (true) {
                        if (s1.peek().equals("(")) {
                            break;
                        }
                        s2.push(s1.pop());
                    }
                    s1.pop();
                } else {
                    if (priority(s1.peek()) < priority(elem)) {
                        s1.push(elem);
                    } else {
                        while (true) {
                            if (priority(s1.peek()) <= priority(elem)) {
                                break;
                            }
                            s2.push(s1.pop());
                        }
                        s1.push(elem);
                    }
                }
            } else {
                s2.push(elem);
            }
        }
        while (true) {
            if (s1.empty()) {
                break;
            }
            s2.push(s1.pop());
        }
        while (true) {
            if (s2.isEmpty()) {
                break;
            }
            s1.push(s2.pop());
        }
        ArrayList<String> newList = new ArrayList<>();
        while (!s1.isEmpty()) {
            newList.add(s1.pop());
        }
        System.out.println(newList);
    }
    //写一个判断是否为符号的方法
    public static boolean isOper(String elem) {
        return elem.equals("+") || elem.equals("-") || elem.equals("*") || elem.equals("/") || elem.equals("(") || elem.equals(")");
    }
    //符号的优先级
    public static int priority(String elem) {
        int res = -1;
        if (elem.equals("-") || elem.equals("+")) {
            res = 1;
        } else if (elem.equals("*") || elem.equals("/")) {
            res = 2;
        } else if (elem.equals("(")) {
            res = -1;
        } else {
            throw new RuntimeException("表达式有误！");
        }
        return res;
    }
    //将expression表达是转化成一个ArrayList对象
    public static List<String> toInFixExpression(String expression) {
        List<String> ArrayList = new ArrayList<>();
        String elem;
        String item = "";
        for (int i = 0; i < expression.length(); i++) {
            elem = expression.substring(i, i + 1);
            if (isOper(elem)) {
                ArrayList.add(elem);
            } else {
                item += elem;
                if (i < expression.length() - 1) {
                    while (!isOper(expression.substring(i + 1, i + 2))) {
                        i++;
                        elem = expression.substring(i, i + 1);
                        item += elem;
                    }
                }
                ArrayList.add(item);
                item = "";
            }
        }
        return ArrayList;
    }
}
